package list

import (
	"fmt"
	"gitee.com/kklt1996/data-structure/common"
)

/*
	单项链表中的元素
*/
type node struct {
	// 节点的值
	value interface{}
	// 下一个元素的指针
	next *node
}

/*
	单项链表
	单项链表的优势是节省存储空间
*/
type LinkedList struct {
	/*
		为了使得添加add第一个元素和add其他元素逻辑一致，使用一个无用的头元素
	*/
	dummyHead *node
	size      int
}

/*
	获取链表的大小
*/
func (linkedList LinkedList) GetSize() int {
	return linkedList.size
}

/*
	获取链表是否为空
*/
func (linkedList LinkedList) IsEmpty() bool {
	return linkedList.size == 0
}

/*
 	O(n)
	在某个位置添加元素
*/
func (linkedList *LinkedList) Add(index int, value ...interface{}) error {
	// 只能在元素的首部和者尾部范围内添加元素
	if index < 0 || index > linkedList.size {
		return common.IndexError{}
	}
	// 不需要添加元素的时候直接返回结果
	if len(value) == 0 {
		return nil
	}
	// 获取到第index-1个元素
	prevNode := linkedList.node(index - 1)
	// 将要插入的元素链接成链表
	insertHead, insertTail := linkedNode(value)
	// 在index-1后面插入新的链表
	next := prevNode.next
	// 在index-1位置链接上要插入链表的头部
	prevNode.next = insertHead
	// 在要插入链表的尾部链接上第index个节点
	insertTail.next = next
	// 元素个数+要填入的元素
	linkedList.size += len(value)
	return nil
}

/*
	O(len(value))
	在链表的头部添加元素
*/
func (linkedList *LinkedList) AddFirst(value ...interface{}) {
	_ = linkedList.Add(0, value...)
}

/*
	O(len(value))
	在链表的尾部添加元素
*/
func (linkedList *LinkedList) AddLast(value ...interface{}) {
	_ = linkedList.Add(linkedList.size, value...)
}

/*
	O(n)
	获取第index个元素
*/
func (linkedList LinkedList) Get(index int) (interface{}, error) {
	// 校验获取的范围是否超出索引
	if index < 0 || index > linkedList.size-1 {
		return nil, common.IndexError{}
	}
	return linkedList.node(index).value, nil
}

/*
	O(1)
	获取链表的第一个元素
*/
func (linkedList LinkedList) GetFirst() (interface{}, error) {
	return linkedList.Get(0)
}

/*
	O(n)
	获取链表的最后一个元素
*/
func (linkedList LinkedList) GetLast() (interface{}, error) {
	return linkedList.Get(linkedList.size - 1)
}

/*
	O(n)
	设置元素的值
*/
func (linkedList *LinkedList) Set(index int, value interface{}) error {
	if index < 0 || index > linkedList.size-1 {
		return common.IndexError{}
	}
	node := linkedList.node(index)
	node.value = value
	return nil
}

/*
	O(n)
	检查是否包含某一个元素值
*/
func (linkedList LinkedList) Contains(value interface{}) bool {

	for cur := linkedList.dummyHead.next; cur != nil; cur = cur.next {
		if value == cur.value {
			return true
		}
	}
	return false
}

/*
	O(n)
	删除第index位置的的元素
*/
func (linkedList *LinkedList) Remove(index int) (interface{}, error) {
	if index < 0 || index > linkedList.size-1 {
		return nil, common.IndexError{}
	}
	// 获取第index-1个元素
	prev := linkedList.node(index - 1)
	// 获取要替换的元素
	retNode := prev.next
	value := retNode.value
	// 替换当前元素
	prev.next = retNode.next
	// 置空当前元素
	retNode.next = nil
	retNode.value = nil
	// size-1
	linkedList.size--
	// 返回元素
	return value, nil
}

/*
	O(1)
	删除第一个元素
*/
func (linkedList *LinkedList) RemoveFirst() (interface{}, error) {
	return linkedList.Remove(0)
}

/*
	O(n)
	删除最后一个元素
*/
func (linkedList *LinkedList) RemoveLast() (interface{}, error) {
	return linkedList.Remove(linkedList.size - 1)
}

/*
	O(n)
	删除某个某个元素值
*/
func (linkedList *LinkedList) RemoveElement(value interface{}) {
	// 寻找要删除的元素
	var removeNode *node
	prev := linkedList.dummyHead
	for prev.next != nil {
		if prev.next.value == value {
			removeNode = prev.next
			break
		}
		prev = prev.next
	}
	// 删除元素
	if removeNode != nil {
		prev.next = removeNode.next
		removeNode.next = nil
		removeNode.value = nil
		linkedList.size--
	}
}

/*
	O(n)
	根据条件删除节点
*/
func (linkedList *LinkedList) RemoveIfMatch(matchFunc func(value interface{}) bool) int {
	removeNum := 0
	prev := linkedList.dummyHead
	for prev.next != nil {
		if matchFunc(prev.next.value) {
			// 获取要删除的节点
			removeNode := prev.next
			// 删除节点
			prev.next = removeNode.next
			// 消除删除的节点和下一个节点的链接
			removeNode.next = nil
			removeNode.value = nil
			removeNum++
		} else {
			// 获取下一个要盘算是否删除的节点
			prev = prev.next
		}
	}
	// 更新元素个数
	linkedList.size -= removeNum
	return removeNum
}

/*
	O(n)
	删除所有节点值等于value的节点
*/
func (linkedList *LinkedList) RemoveAllElement(value interface{}) int {
	return linkedList.RemoveIfMatch(func(nodeValue interface{}) bool {
		return nodeValue == value
	})
}

/*
	可以删除和设置节点值的迭代器
*/
func (linkedList *LinkedList) Iterator(iteratorFunc func(iterator common.Iterator) bool) {
	linkedListIterator := &LinkedListIterator{linkedList: linkedList}
	var iterator common.Iterator = linkedListIterator
	prev := linkedList.dummyHead
	for prev.next != nil {
		linkedListIterator.removeFlag = false
		linkedListIterator.prev = prev
		linkedListIterator.node = prev.next
		if iteratorFunc(iterator) {
			break
		} else {
			// 没有删除元素的话需要prev.next后移,删除的话删除的时候prev.next已经后移了
			if !iterator.(*LinkedListIterator).removeFlag {
				// 获取下一个要判断是否删除的节点
				prev = prev.next
			}
		}
	}
}

/*
	O(n)
	对链表进行循环处理
	func(value interface{}) bool
	bool 表示是否终止循环
*/
func (linkedList *LinkedList) Foreach(foreachFunc func(index int, value interface{}) bool) {
	index := 0
	for cur := linkedList.dummyHead.next; cur != nil; cur = cur.next {
		if foreachFunc(index, cur.value) {
			break
		}
		index++
	}
}

/*
	将链表转换成切片
*/
func (linkedList *LinkedList) ToSlice() []interface{} {
	res := make([]interface{}, 0, linkedList.size)
	for cur := linkedList.dummyHead.next; cur != nil; cur = cur.next {
		res = append(res, cur.value)
	}
	return res
}

/*
	O(n)
	字符串打印
*/
func (linkedList LinkedList) String() string {
	var res string
	for cur := linkedList.dummyHead.next; cur != nil; cur = cur.next {
		res += fmt.Sprintf("%v->", cur.value)
	}
	res += "NIL"
	return res
}

/*
	查找index位置的上一个节点  index=[-1,size-1]
*/
func (linkedList LinkedList) node(index int) *node {
	node := linkedList.dummyHead
	for i := -1; i < index; i++ {
		// 获取链表的下一个元素
		node = node.next
	}
	return node
}

/*
	将节点进行链接
*/
func linkedNode(value []interface{}) (*node, *node) {
	var insertHead *node
	var insertTail *node
	for _, v := range value {
		if insertTail == nil {
			insertTail = &node{v, nil}
			insertHead = insertTail
		} else {
			insertTail.next = &node{v, nil}
			insertTail = insertTail.next
		}
	}
	return insertHead, insertTail
}

/*
	linkedList迭代器,用于再遍历的过程中删除元素和修改元素
*/
type LinkedListIterator struct {
	linkedList *LinkedList
	// 当前节点
	node *node
	// 当前节点的上一个节点
	prev *node
	// 是否删除了节点
	removeFlag bool
}

/*
	删除节点
*/
func (iterator *LinkedListIterator) Remove() {
	if iterator.removeFlag {
		return
	}
	// 删除节点
	iterator.prev.next = iterator.node.next
	// 消除删除的节点和下一个节点的链接
	iterator.node.next = nil
	iterator.node.value = nil
	// 节点个数-1
	iterator.linkedList.size--
	// 标记标识删除了元素
	iterator.removeFlag = true
}

/*
	修改节点的值
*/
func (iterator LinkedListIterator) Set(value interface{}) error {
	if iterator.removeFlag {
		return common.OperatorNotUseful{}
	}
	iterator.node.value = value
	return nil
}

/*
	获取value
*/
func (iterator LinkedListIterator) Get() (interface{}, error) {
	if iterator.removeFlag {
		return nil, common.OperatorNotUseful{}
	}
	return iterator.node.value, nil
}
